package com.chj.gaoji.class07;

import java.util.Arrays;

public class Code04_StrangePrinter {
	public static int strangePrinter(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int[][] dp = new int[N][N];
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
			dp[i][i] = 1;
			dp[i][i + 1] = str[i] == str[i + 1] ? 1 : 2;
		}
		for (int i = N - 2; i >= 0; i--) {
			for (int j = i + 2; j < N; j++) {
				dp[i][j] = j - i + 1;
				for (int k = i + 1; k <= j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k][j] - (str[i] == str[k] ? 1 : 0));
				}
			}
		}
		return dp[0][N - 1];
	}

//	https://www.cnblogs.com/grandyang/p/8319913.html
	public static int strangePrinter2(String s) {
		char[] ss = s.toCharArray();
		int n = ss.length;
		int[][] dp = new int[n][n];

		for (int i = n - 1; i >= 0; i--) {
			for (int j = i; j < n; j++) {
				if (i == j) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = 1 + dp[i + 1][j];
				}
				for (int k = i + 1; k <= j; k++) {
					if (ss[k] == ss[i])
						dp[i][j] = Math.min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]);
				}
			}
		}
		return (n == 0) ? 0 : dp[0][n - 1];
	}

	public static int strangePrinter3(String s) {
		char[] ss = s.toCharArray();
		int n = ss.length;
		int[][] memo = new int[n][n];
		return helper3(ss, 0, n - 1, memo);
	}

	public static int helper3(char[] s, int i, int j, int[][] memo) {
		if (i > j)
			return 0;
		if (memo[i][j] > 0) {
			return memo[i][j];
		}
		memo[i][j] = helper3(s, i + 1, j, memo) + 1;
		for (int k = i + 1; k <= j; ++k) {
			if (s[i] == s[k]) {
				memo[i][j] = Math.min(memo[i][j], helper3(s, i + 1, k - 1, memo) + helper3(s, k, j, memo));
			}
		}
		return memo[i][j];
	}

	public static int strangePrinter4(String s) {

		char[] ss = s.toCharArray();
		int n = ss.length;
		if (n == 0)
			return 0;
		int[][] dp = new int[n + 1][n + 1];

		for (int i = 0; i < n; i++) {
			dp[i][i] = 1;
		}
		for (int len = 2; len <= n; len++) {
			for (int i = 0; i + len - 1 < n; i++) {
				int j = i + len - 1;
				dp[i][j] = dp[i + 1][j] + 1;
				for (int k = i + 1; k <= j; k++) {
					if (ss[i] == ss[k])
						dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);
				}
			}
		}
		return dp[0][n - 1];
	}

	public static int strangePrinter5(String s) {
		char[] cs = s.toCharArray();
		int n = cs.length;
		if (n == 0)
			return 0;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], 1000000);
			dp[i][i] = 1;
		}

		for (int len = 2; len <= n; len++) {
			for (int i = 0; i + len - 1 < n; i++) {
				int j = i + len - 1;
				for (int k = i; k <= j; k++) {
					if (cs[i] == cs[k]) {
						dp[i][j] = Math.min(dp[i][j], (k > i ? dp[i][k - 1] : dp[i][i]) + (k < j ? dp[k + 1][j] : 0));
					} else {
						dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k < j ? dp[k + 1][j] : 0));
					}
				}
			}
		}
		return dp[0][n - 1];
	}

	public static void main(String[] arg) {
		System.out.println(strangePrinter("aba"));
		System.out.println(strangePrinter("aaabbb"));
		System.out.println(strangePrinter2("aba"));
		System.out.println(strangePrinter2("aaabbb"));
		System.out.println(strangePrinter3("aba"));
		System.out.println(strangePrinter3("aaabbb"));
		System.out.println(strangePrinter4("aba"));
		System.out.println(strangePrinter4("aaabbb"));
		System.out.println(strangePrinter5("aba"));
		System.out.println(strangePrinter5("aaabbb"));
	}

}
